﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MapColoring.MontadorMapa;
using MapColoring.CSP;

namespace MapColoring
{
    /// <summary>
    /// Trabalho PCS2059
    /// 
    /// André Martini Diniz     5691310
    /// Danilo Elias da Silva   5690598
    /// 
    /// Russel, S. and Norvig, P. (2003) Artificial Intelligence: a modern approach. Prentice Hall. 2nd. Edition
    /// Ex. 5.7, pg. 159 (CSP on map coloring)
    /// 
    /// Figure 5.5 tests out various algorithms on the n-queens problem. Try these same algorithms
    /// on map-coloring problems generated randomly as follows: scatter n points on the
    /// unit square; selecting a point X at random, connect X by a straight line to the nearest point
    /// Y such that X is not already connected to Y and the line crosses no other line; repeat the
    /// previous step until no more connections are possible. Construct the performance table for the
    /// largest n you can manage, using both d = 3 and d = 4 colors. Comment on your results.
    /// </summary>
    class Program
    {
        public static int nIteracoes = 0;

        static void Main(string[] args)
        {
            //Para debug
            //testeIterativo();

            int MAX_NUM_INTERACOES = 50000;
            System.Console.WriteLine("----------------------------------------------------------------");
            System.Console.WriteLine("-----                                                       ----");
            System.Console.WriteLine("-----     PCS2059 - CSP on Map Coloring                     ----");
            System.Console.WriteLine("-----     André Martini Diniz   5691310                     ----");
            System.Console.WriteLine("-----     Danilo Elias da Silva 5690598                     ----");
            System.Console.WriteLine("-----                                                       ----");
            System.Console.WriteLine("----------------------------------------------------------------");
            System.Console.WriteLine("");            

            while (true)
            {

                //Dados de Entrada
                System.Console.Write("Especifique o número de pontos a serem gerados no mapa:");
                int nPontos = Int16.Parse(System.Console.ReadLine());
                System.Console.Write("Especifique o valor do seed para o rng:");
                int seed = Int32.Parse(System.Console.ReadLine());

                Random rng = new Random(seed);

                Mapa mapa = new Mapa();
                mapa.montarMapa(nPontos, rng);

                System.Console.Write("Especifique o número de cores que podem ser atribuídas (3 ou 4):");
                int nCores = Int32.Parse(System.Console.ReadLine());

                CSP.CSP csp = new CSP.CSP(nCores, mapa);
                
                //se for possível resolver o mapa, calcula os tempos
                if (csp.fowardCheckingMRV())
                {
                    System.Console.WriteLine("--------------");
                    System.Console.WriteLine("O mapa gerado possui solução!");
                    System.Console.WriteLine("");
                    System.Console.WriteLine("Desempenho dos Algoritmos:");

                    System.Console.Write("BacktrackSearch:             ");
                    Program.nIteracoes = 0;
                    csp = new CSP.CSP(nCores, mapa);
                    csp.backtrackingSearch();
                    System.Console.WriteLine(Program.nIteracoes);

                    System.Console.Write("BacktrackSearch com MRV:     ");
                    csp = new CSP.CSP(nCores, mapa);
                    Program.nIteracoes = 0;
                    csp.backtrackingSearchMRV();
                    System.Console.WriteLine(Program.nIteracoes);

                    System.Console.Write("ForwardChecking:             ");
                    csp = new CSP.CSP(nCores, mapa);
                    Program.nIteracoes = 0;
                    csp.fowardChecking();
                    System.Console.WriteLine(Program.nIteracoes);

                    System.Console.Write("ForwardChecking com MRV:     ");
                    csp = new CSP.CSP(nCores, mapa);
                    Program.nIteracoes = 0;
                    csp.fowardCheckingMRV();
                    System.Console.WriteLine(Program.nIteracoes);

                    System.Console.Write("Busca Local (Min-conflicts): ");
                    csp = new CSP.CSP(nCores, mapa);
                    Program.nIteracoes = 0;
                    csp.minConflicts(MAX_NUM_INTERACOES);
                    System.Console.WriteLine(Program.nIteracoes);
                }
                else
                {
                    System.Console.Write("O mapa gerado não possui solução para o número de cores fornecido.");
                }

                System.Console.WriteLine("");
                System.Console.WriteLine("");
                System.Console.WriteLine("");
                System.Console.WriteLine("------------------------------------------------------------------");
                System.Console.WriteLine("Reinicializando...");
            }
        }

        /// <summary>
        /// Testa iterativamente até não encontrar mais soluções viáveis para aquele número de pontos
        /// </summary>
        static public void testeIterativo()
        {
            int nPontos3 = 50;
            int nPontos4 = 50;
            int seed = 0;
            int seedSolucao3 = 0;
            int seedSolucao4 = 0;
            bool achouSolucao = true;
            while (seed <= 20000)
            {
                Random rng = new Random(seed);

                Mapa mapa = new Mapa();
                mapa.montarMapa(nPontos3, rng);

                CSP.CSP csp = new CSP.CSP(3, mapa);
                achouSolucao = csp.fowardCheckingMRV();

                if (!achouSolucao)
                {
                    seed += 1;
                }
                else
                {
                    nPontos3 += 1;
                    seedSolucao3 = seed;
                    seed = 1;
                    break;
                }
            }

            seed = 0;

            while (seed <= 20000)
            {
                Random rng = new Random(seed);

                Mapa mapa = new Mapa();
                mapa.montarMapa(nPontos4, rng);

                CSP.CSP csp = new CSP.CSP(4, mapa);
                achouSolucao = csp.fowardCheckingMRV();

                if (!achouSolucao)
                {
                    seed += 1;
                }
                else
                {
                    nPontos4 += 1;
                    seedSolucao4 = seed;
                    seed = 1;
                }
            }
        }
    }
}
